package listnode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author kaho
 * @create 2020/11/25
 */
public class _23_合并K个升序链表 {


    /**
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0 ) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(v -> v.val));
        for (ListNode list : lists) {
            if (list!=null) {
                heap.offer(list);
            }
        }

        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!heap.isEmpty()){
            ListNode poll = heap.poll();
            tail.next = poll;
            tail = tail.next;
            if (poll.next!=null) {
                heap.offer(poll.next);
            }
        }
        return dummy.next;
    }
}
